package cn.algorithm.sort;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

/**
 * 快速排序：使用分治法的算法思想，每轮选择一个基准元素，将数列与基准元素比较，比基准元素大的移动到数列一边，
 * 小的移动到另一边，形成两个部分，在对这两部分数列进行之前的操作，直至不能拆分为止
 * 1、双边循环法
 * 2、单边循环法
 * 3、使用栈实现
 *
 * @author dunlingiz
 * @date 2024/3/6
 * @since v
 */
public class QuickSort {

    /**
     * 用递归实现
     */
    public static void sort(int[] arr, int startIndex, int endIndex) {
        System.out.println("比较的数组；startIndex:" + startIndex + "  endIndex:" + endIndex);
        if (startIndex >= endIndex || endIndex < 0) {
            return;
        }
        // 双边循环法
        //int pivotIndex = bilateralPartition(arr, startIndex, endIndex);
        // 单边循环法
        int pivotIndex = unilateralPartition(arr, startIndex, endIndex);
        // 递归的形式
        sort(arr, startIndex, pivotIndex - 1);
        sort(arr, pivotIndex + 1, endIndex);
    }

    /**
     * 优化
     */
    public static void sortOption(int[] arr, int startIndex, int endIndex) {
        System.out.println("比较的数组；startIndex:" + startIndex + "  endIndex:" + endIndex);
        if (startIndex >= endIndex) {
            return;
        }
        // 双边循环法
        //int pivotIndex = bilateralPartition(arr, startIndex, endIndex);
        // 单边循环法
        int pivotIndex = unilateralPartition(arr, startIndex, endIndex);
        // 用于排除不正确的递归拆分，例如 startIndex=0 endIndex=-1、startIndex=3 endIndex=2等等
        if (startIndex < pivotIndex - 1) {
            sortOption(arr, startIndex, pivotIndex - 1);
        }
        if (endIndex > pivotIndex + 1) {
            sortOption(arr, pivotIndex + 1, endIndex);
        }
    }

    /**
     * 用栈实现
     */
    public static void stackSort(int[] arr, int startIndex, int endIndex) {
        // 使用栈
        Stack<Map<String, Integer>> indexStacks = new Stack<>();
        Map<String, Integer> root = new HashMap<>();
        root.put("startIndex", startIndex);
        root.put("endIndex", endIndex);
        indexStacks.push(root);
        // 循环栈
        while (!indexStacks.isEmpty()) {
            Map<String, Integer> index = indexStacks.pop();
            int start = index.get("startIndex");
            int end = index.get("endIndex");
            System.out.println("比较的数组；start:" + start + "  end:" + end);
            // 排序
            int pivotIndex = unilateralPartition(arr, start, end);
            // 分割成两部分进行排序比较
            if (start < pivotIndex - 1) {
                Map<String, Integer> leftRoot = new HashMap<>();
                leftRoot.put("startIndex", start);
                leftRoot.put("endIndex", pivotIndex - 1);
                indexStacks.push(leftRoot);
            }
            if (end > pivotIndex + 1) {
                Map<String, Integer> rightRoot = new HashMap<>();
                rightRoot.put("startIndex", pivotIndex + 1);
                rightRoot.put("endIndex", end);
                indexStacks.push(rightRoot);
            }
        }
    }


    /**
     * 双边循环法
     */
    private static int bilateralPartition(int[] arr, int startIndex, int endIndex) {
        // 选择基准元素
        int pivot = arr[startIndex];
        int left = startIndex;
        int right = endIndex;

        //当左指针不等于右指针
        while (left != right) {
            // 需要满足右指针的元素大于基准元素，移动右指针，否则就暂停移动指针
            while (left < right && arr[right] > pivot) {
                right--;
            }
            // 左指针从数组首位往后进行比较，需要满足左指针的元素大于基准元素，移动左指针，否则就暂停移动指针
            while (left < right && arr[left] <= pivot) {
                left++;
            }
            // 将左右指针的数据进行交换， 左指针小于右指针的情况
            if (left < right) {
                int temp = arr[left];
                arr[left] = arr[right];
                arr[right] = temp;
            }
        }
        if (startIndex == left) {
            return left;
        }
        arr[startIndex] = arr[left];
        arr[left] = pivot;
        return left;
    }

    /**
     * 单边循环法
     */
    public static int unilateralPartition(int[] arr, int startIndex, int endIndex) {
        // 选择基准元素
        int pivot = arr[startIndex];
        //指针
        int mark = startIndex;
        //从开始索引 + 1到结束索引进行循环数列，将当前元素与基准元素比较交换
        for (int i = startIndex + 1; i <= endIndex; i++) {
            // 当前元素小于基准元素，mark进行自增，并则将mark索引位置的元素与当前元素进行交换，
            // 确保以mark指针索引为界，小于基准元素的数列位于mark位置的左边，大于基准元素的数列位于mark位置的右边
            if (arr[i] < pivot) {
                mark++;
                int temp = arr[mark];
                arr[mark] = arr[i];
                arr[i] = temp;
            }
        }
        // 将数列头与mark位置的元素进行交换
        if (startIndex == mark) {
            return mark;
        }
        arr[startIndex] = arr[mark];
        arr[mark] = pivot;
        return mark;
    }
}
